package hl.leco.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 
 * @author Liu Huan
 */

/**
 * 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。
 * 由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。
 * 开始坐标总是小于结束坐标。平面内最多存在104个气球。
 *
 * 一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标
 * 为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。
 * 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
 *
 * Example:
 *
 * 输入:
 * [[10,16], [2,8], [1,6], [7,12]]
 *
 * 输出:
 * 2
 *
 * 解释:
 * 对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
 *
 */
public class MinArrays {
	public static void main(String[] args) {
		int[][] boll = {{10,16}, {2,8}, {1,6}, {7,12}};
		System.out.println("最少的箭数：" + findMinArrowShots(boll));
	}
	
	public static int findMinArrowShots(int[][] points) {
		// 打印 气球位置
		System.out.println("points = " + Arrays.deepToString(points));
		
		// 如果气球数为0，返回0个箭
		if(points.length == 0) return 0;
		
		// 根据 x_end 升序排列气球： o1-o2 是升序，o2 - o1 是降序
		Arrays.sort(points, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1]-o2[1];
			}
		});
		// 打印 气球位置信息
		System.out.println("points = " + Arrays.deepToString(points));;
		
		// 初始化箭数为 1
		int arrows = 1;
		// 定义箭的发射位置，默认取第一个气球的 x_end 坐标
		int position = points[0][1];
		// 遍历气球
		for(int[] p : points) {
			// 如果当前气球的开始坐标 x_start 大于 弓箭发射位置
			if(p[0] > position){
				arrows++;// 增加一个箭的数量
				position = p[1];// 更新 箭发射的位置
			}
		}
		return arrows;
	}
}
